package codingInterview.leetcode.editor.cn;

//输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。 
//
// 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
//
// 
//
// 示例 1: 
//
// 
//Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//Output: [3,9,20,null,null,15,7]
// 
//
// 示例 2: 
//
// 
//Input: preorder = [-1], inorder = [-1]
//Output: [-1]
// 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-
//preorder-and-inorder-traversal/ 
// Related Topics 树 数组 哈希表 分治 二叉树 👍 677 👎 0

import java.util.Arrays;
import java.util.TreeMap;

//Java：剑指 Offer 07 - 重建二叉树
public class ZhongJianErChaShuLcof{
    public static void main(String[] args) {
                Solution solution = new ZhongJianErChaShuLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return analyze(preorder,inorder, 0,0,preorder.length);
    }

    /**
     *
     * @param preorder 原前序遍历序列
     * @param inorder 原中序遍历序列
     * @param preIndex 子序列在原前序 中的起始位置
     * @param inIndex 子序列在原中序 中的起始位置
     * @param length 子序列长度
     * @return
     */
    TreeNode analyze(int[] preorder, int[] inorder, int preIndex,int inIndex, int length){
        if(length == 0) return null; // 输入的序列为空：说明这是一个空节点
        if(length == 1) return new TreeNode(preorder[preIndex]); // 终止条件：输入的序列只有一个值。
        TreeNode root = new TreeNode(preorder[preIndex]); // 根节点为前序的第一个
        int leftLength=0, rightLength=0;
        for (int i = 0; i < length; i++) {
            if (inorder[inIndex+i] == root.val){ // 找到根节点的位置，划分为左右
                leftLength = i;
                rightLength = length-1-i;
                break;
            }
//            System.out.println(Arrays.toString(Arrays.copyOfRange(preorder, preIndex,preIndex+leftLength))+" - "
//                    +Arrays.toString(Arrays.copyOfRange(preorder, preIndex+leftLength+1,preIndex+leftLength)));
        }
//        if(leftLength !=0)
            root.left = analyze(preorder, inorder, preIndex+1, inIndex, leftLength);
//        if (rightLength !=0)
            root.right = analyze(preorder, inorder, preIndex+leftLength+1, inIndex+leftLength+1, rightLength);
        return root;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
